import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/9 9:53
 * @description 前缀树
 */
public class Solution2 {
    public static void main(String[] args) {

    }

    public List<String> findRepeatedDnaSequences(String s) {
        Trie root = new Trie();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < s.length() - 9; i++) {
            if (built(s, i, root)) {
                set.add(s.substring(i, i + 10));
            }
        }
        return new ArrayList<>(set);
    }

    public boolean built(String s, int start, Trie node) {
        for (int i = start; i < start + 10; i++) {
            char c = s.charAt(i);
            if (node.arr[c - 'A'] == null) {
                node.arr[c - 'A'] = new Trie();
            }
            node = node.arr[c - 'A'];
        }
        if (!node.isEnd) {
            node.isEnd = true;
            return false;
        }
        return true;
    }
}

class Trie {
    boolean isEnd = false;
    Trie[] arr = new Trie[26];
}
